package com.algorithm3;

import java.util.Arrays;

public class HeapSort {

    public static void heapSort(int[] array){
        buildHeap(array,array.length-1);//构建堆
        //堆化排序
        int index = array.length-1;
        while(index>0){
            swap(array,index,1);
          /*  int temp = array[index];
            array[index] = array[1];
            array[1] = temp;*/
            index--;
            heapify(array,index,1);
        }
        System.out.println("堆排序结果:" + Arrays.toString(array));

    }
    public static void buildHeap(int[] array,int len){
        for(int i=len/2;i>0;i--){
            heapify(array,len,i);
        }

    }

    public static void heapify(int[] array,int len,int k){
        int left = 2*k;
        int right = 2*k+1;
        int maxP = k;
        if(len>left && array[left]>array[maxP]){
            maxP = left;
        }
        if(len>right && array[right]>array[maxP]){
            maxP = right;
        }
        if(maxP!=k){
            swap(array,maxP,k);
            heapify(array,len,maxP);
            System.out.println("k为："+"-->"+k +"-->"+ Arrays.toString(array));
        }

    }
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        //buildHeap(array,array.length-1);
        //System.out.println("构建堆:" + Arrays.toString(array));
        heapSort(array);
    }
}
